package com.tucc.hello.offer.no38;

import java.util.*;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        String[] result = solution.permutation("kzfxxx");
        Set<String> set = new HashSet<>();
        for (String str : result) {
            System.out.print(str + " ");
            set.add(str);
        }
        System.out.println();
        System.out.println(result.length);
        System.out.println(set.size());
    }

    public String[] permutation(String s) {
        List<String> result = new ArrayList<>();
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        permutation(chars, chars.length, result);
        return result.toArray(new String[0]);
    }


    public void permutation(char[] chars, int size, List<String> result) {
        if (size == 0) {
            if (chars.length > 0) {
                result.add(new String(chars));
            }
        } else {
            Set<Character> used = new HashSet<>();
            for (int i = 0; i < size; i++) {
                if (used.add(chars[i])) {
                    swap(chars, i, size - 1);
                    permutation(chars, size - 1, result);
                    swap(chars, i, size - 1);
                }
                while (i + 1 < size) {
                    if (chars[i + 1] == chars[i]) {
                        i++;
                    } else {
                        break;
                    }
                }
            }
        }

    }

    public boolean swap(char[] chars, int x, int y) {
        if (x != y && chars[x] != chars[y]) {
            char ch = chars[x];
            chars[x] = chars[y];
            chars[y] = ch;
            return true;
        }
        return false;
    }
}
